List of papers and topics

More on classical CSPs

• Strong subalgebras: https://arxiv.org/abs/2005.00593
  Strong subalgebras form the backbone of Zhuk’s proof of the Feder-Vardi dichotomy conjecture. This paper, that appeared after the proof, is a must-read to understand the ideas behind Zhuk’s algorithm.
• Minimal Taylor Algebras: https://arxiv.org/abs/2104.11808
  Minimal Taylor algebras are those algebras corresponding to CSPs that are in P but maximally so: any properly harder CSP must be NP-complete.
• Wonderland of reflections: https://arxiv.org/abs/1510.04521
  An abstract theory of “minion homomorphisms” (in this paper originally called “height 1 clone homomorphisms”) that is relevant to infinite-domain CSPs and that is one of the foundation of the current theory of PCSPs.
• CSPs with operations and relations: https://arxiv.org/abs/2010.04958
  In the original framework, the template of a CSP only includes relations – it is a relational structure. In this work, CSPs with functions are considered and a connection with tame congruence theory is developped. These results have been generalized but not in a published form.

Despite the Bulatov-Zhuk theorem some topics remain open for finite-domain CSPs. In particular the NL-conjecture is open, see Polymorphisms and How to Use Them (https://drops.dagstuhl.de/opus/volltexte/2017/6959/pdf/DFU-Vol7-15301-1.pdf), Conjecture 50 and attached references.

Infinite-domain CSPs

For infinite-domain CSPs, one focuses on specific classes of structures $\mathbb A$ and try to obtain new algorithmic/algebraic results. One of the central concepts is that of $\omega$-categoricity, which is a property of $\mathbb A$ that is sufficient for the complexity of CSP($\mathbb A$) to be characterized by Pol($\mathbb A$).

• Structural properties of (finite and) omega-categorical digraphs with good polymorphisms: https://arxiv.org/abs/2302.12112

A theory of “smooth approximations” was developped recently to unify the existing results in infinite-domain constraint satisfaction:

• Smooth approximations: https://arxiv.org/abs/2011.03978
• Smooth approximations 2: https://arxiv.org/abs/2102.07531

Polymorphisms of $\omega$-categorical structures can be wild. Usually, one uses some Ramsey-theoretic arguments to simply such polymorphisms. This is possible when the underlying structure (or an expansion thereof) satisfies the “Ramsey property”.

• Cores over Ramsey structures: https://arxiv.org/abs/2004.05936
• How to use the Ramsey property to obtain canonical (i.e., simple) functions: https://arxiv.org/abs/1610.09660

Promise CSPs

PCSPs are problems parametrized by two relational structure $\mathbb A,\mathbb B$ such that there exist a homomorphism $\mathbb A\to\mathbb B$. The problem PCSP($\mathbb A,\mathbb B$) takes as input $\mathbb X$, and the goal is to decide between

• YES: there exists a homomorphism $\mathbb X\to\mathbb A$,
• NO: there does not exist a homomorphism $\mathbb X\to\mathbb A$.

There has been a lot of papers in the recent years about this topic. Small excerpt of the relevant literature:

• Initial ground theory that was established to give an algebraic formalism to the study of PCSPs: https://arxiv.org/abs/1811.00970
• Recent survey on Promise CSP: https://arxiv.org/abs/2208.13538

PCSPs that are known to be in P are usually solved by one of the following methods, or a specific mixture thereof: either use the basic linear programming relaxation (BLP), or use the affine integer programming relaxation (AIP).
Algorithmic results:

• CLAP: a new algorithm for PCSP: https://arxiv.org/abs/2107.05018
  CLAP is one particular example of an algorithm combining BLP and AIP.
• Robust satisfiability and Semi-definite programming: https://arxiv.org/abs/2211.08373
  Semi-definite programming is a third type of relaxation whose expressive power is not quite understood.
• The Sherali-Adams Hierarchy and Tensors: https://arxiv.org/abs/2203.02478
  The Sherali-Adams hierarchy is a hierarchy of linear programming relaxations, whose bottom level is BLP.
• Characterization of the algorithm “BLP+AIP” combining linear programming and integer programming: https://arxiv.org/abs/1907.04383

Classification results (of the form “Given a specific class of PCSPs, describe the border between Ptime and NP-hard PCSPs”):

• Beyond PCSP(1-in-3, NAE): https://arxiv.org/abs/2104.12800
• Classification for $PCSP(\hat{\mathbb A},\hat{\mathbb B})$, where $\mathbb A$ and $\mathbb B$ are graphs: https://arxiv.org/abs/2302.03456
• Boolean ordered PCSPs: https://arxiv.org/abs/2102.11854